/*
 * @(#) $Header$
 *
 * Copyright (C) 2006  Daniel Léonard
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 */

package ca.forklabs.baselib.util;

import java.util.Iterator;
import java.util.ListIterator;

import ca.forklabs.baselib.util.UnaryFunction;

/**
 * Class {@link Algorithm} provides algorithms similar to the C++ header
 * {@code <algorithm>}.
 *
 * @author   <a href="mailto:forklabs at gmail.com?subject=ca.forklabs.baselib.util.Algorithm">Daniel Léonard</a>
 * @version $Revision$
 */
public class Algorithm {

//---------------------------
// Constructor
//---------------------------

   /**
    * Let no one instanciate this class.
    */
   protected Algorithm() {
   // do nothing
      }


//---------------------------
// forEach()
//---------------------------

   /**
    * Invokes the function on each element of the iterator.
    * @param   source   the iterator.
    * @param   function   the function to invoke.
    * @param   <A>   the type of the argument object.
    * @return   <code>function</code>.
    */
   public static <A> UnaryFunction<Void, A> forEach(Iterator<A> source, UnaryFunction<Void, A> function) {
      Iterable<A> arguments = Iterators.asIterable(source);
      for (A argument : arguments) {
         function.invoke(argument);
         }
      return function;
      }

   /**
    * Invokes the function on each element of the iterable.
    * @param   source   the iterable.
    * @param   function   the function to invoke.
    * @param   <A>   the type of the argument object.
    * @return   <code>function</code>.
    */
   public static <A> UnaryFunction<Void, A> forEach(Iterable<A> source, UnaryFunction<Void, A> function) {
      function = forEach(source.iterator(), function);
      return function;
      }


//---------------------------
// findIf()
//---------------------------

   /**
    * Finds the first element of the iterator that matches the given predicate.
    * If {@code source} is a {@link ListIterator}, the matched element can be
    * retrieved with {@code source.previous()} as soon as this method has
    * returned.
    * @param   source   the iterator.
    * @param   predicate   the predicate evaluating the elements.
    * @param   <A>   the type of the argument object.
    * @return   {@code true} if there is a match, {@code false} otherwise.
    */
   public static <A> boolean findIf(Iterator<A> source, UnaryPredicate<A> predicate) {
      boolean found = false;

      while ((false == found) && source.hasNext()) {
         A argument = source.next();
         found = predicate.eval(argument);
         }

      return found;
      }

   /**
    * Finds the first element of the iterable that matches the given predicate.
    * @param   source   the iterable.
    * @param   predicate   the predicate evaluating the elements.
    * @param   <A>   the type of the argument object.
    * @return   {@code true} if there is a match, {@code false} otherwise.
    */
   public static <A> boolean findIf(Iterable<A> source, UnaryPredicate<A> predicate) {
      boolean found = findIf(source.iterator(), predicate);
      return found;
      }


//---------------------------
// copy(), copyIf()
//---------------------------

   /**
    * Copies all the elements from the source iterator into the destination
    * iterator. The destination must have enough space to receive its elements.
    * @param   source   the source iterator.
    * @param   destination   the destination iterator.
    * @param   <E>   the type of the elements.
    * @return   the destination iterator.
    */
   public static <E> ListIterator<E> copy(Iterator<E> source, ListIterator<E> destination) {
      UnaryPredicate<E> predicate = Predicates.alwaysTrue();
      ListIterator<E> iterator = Algorithm.copyIf(source, destination, predicate);
      return iterator;
      }

   /**
    * Copies all the elements from the source iterable into the destination
    * iterator. The destination must have enough space to receive its elements.
    * @param   source   the source iterable.
    * @param   destination   the destination iterator.
    * @param   <E>   the type of the elements.
    * @return   the destination iterator.
    */
   public static <E> ListIterator<E> copy(Iterable<E> source, ListIterator<E> destination) {
      ListIterator<E> iterator = Algorithm.copy(source.iterator(), destination);
      return iterator;
      }

   /**
    * Copies all the elements that satisfy the predicate from the source
    * iterator into the destination iterator. The destination must have enough
    * space to receive its elements.
    * @param   source   the source iterator.
    * @param   destination   the destination iterator.
    * @param   predicate   the predicate allowing the copy.
    * @param   <E>   the type of the elements.
    * @return   the destination iterator.
    */
   public static <E> ListIterator<E> copyIf(Iterator<E> source, ListIterator<E> destination, UnaryPredicate<E> predicate) {
      Iterable<E> elements = Iterators.asIterable(source);
      for (E element : elements) {
         boolean copy = predicate.eval(element);
         if (copy) {
            destination.next();
            destination.set(element);
            }
         }
      return destination;
      }

   /**
    * Copies all the elements that satisfy the predicate from the source
    * iterable into the destination iterator. The destination must have enough
    * space to receive its elements.
    * @param   source   the source iterable.
    * @param   destination   the destination iterator.
    * @param   predicate   the predicate allowing the copy.
    * @param   <E>   the type of the elements.
    * @return   the destination iterator.
    */
   public static <E> ListIterator<E> copyIf(Iterable<E> source, ListIterator<E> destination, UnaryPredicate<E> predicate) {
      ListIterator<E> iterator = Algorithm.copyIf(source.iterator(), destination, predicate);
      return iterator;
      }

//---------------------------
// transform()
//---------------------------

   /**
    * Gives each element from the source to the function and store the result
    * into the destination. The destination must have enough space to receive
    * its elements.
    * @param   <R>   the type of the returned object.
    * @param   <A>   the type of the argument object.
    * @param   source   the source iterator.
    * @param   destination   the destination iterator.
    * @param   function   the transformation function.
    * @return   the destination iterator.
    */
   public static <R, A> ListIterator<R> transform(Iterator<A> source, ListIterator<R> destination, UnaryFunction<R, A> function) {
      Iterable<A> arguments = Iterators.asIterable(source);
      for (A argument : arguments) {
         R result = function.invoke(argument);
         destination.next();
         destination.set(result);
         }
      return destination;
      }

   /**
    * Gives each element from the source to the function and store the result
    * into the destination. The destination must have enough space to receive
    * its elements.
    * @param   <R>   the type of the returned object.
    * @param   <A>   the type of the argument object.
    * @param   source   the source iterable.
    * @param   destination   the destination iterator.
    * @param   function   the transformation function.
    * @return   the destination iterator.
    */
   public static <R, A> ListIterator<R> transform(Iterable<A> source, ListIterator<R> destination, UnaryFunction<R, A> function) {
      destination = transform(source.iterator(), destination, function);
      return destination;
      }

   /**
    * Gives one element from each source, one at a time, to the function and
    * store the result into the destination. The destination must have enough
    * space to receive its elements.
    * @param   <R>   the type of the returned object.
    * @param   <A1>   the type of the first argument object.
    * @param   <A2>   the type of the second argument object.
    * @param   source1   the first source iterator.
    * @param   source2   the second source iterator.
    * @param   destination   the destination iterator.
    * @param   function   the transformation function.
    * @return   the destination iterator.
    */
   public static <R, A1, A2> ListIterator<R> transform(Iterator<A1> source1, Iterator<A2> source2, ListIterator<R> destination, BinaryFunction<R, A1, A2> function) {
      while (source1.hasNext() && source2.hasNext()) {
         A1 arg1 = source1.next();
         A2 arg2 = source2.next();
         R result = function.invoke(arg1, arg2);
         destination.next();
         destination.set(result);
         }
      return destination;
      }

   /**
    * Gives one element from each source, one at a time, to the function and
    * store the result into the destination. The destination must have enough
    * space to receive its elements.
    * @param   <R>   the type of the returned object.
    * @param   <A1>   the type of the first argument object.
    * @param   <A2>   the type of the second argument object.
    * @param   source1   the first source iterable.
    * @param   source2   the second source iterable.
    * @param   destination   the destination iterator.
    * @param   function   the transformation function.
    * @return   the destination iterator.
    */
   public static <R, A1, A2> ListIterator<R> transform(Iterable<A1> source1, Iterable<A2> source2, ListIterator<R> destination, BinaryFunction<R, A1, A2> function) {
      destination = transform(source1.iterator(), source2.iterator(), destination, function);
      return destination;
      }

//---------------------------
// remove(), removeIf(), removeCopy()
//---------------------------

   /**
    * Removes all the elements from the collection that are equal to the
    * specified value.
    * @param   <E>   the type of the elements.
    * @param   source   the start of the collection.
    * @param   value   the value to remove from the collection.
    */
   public static <E> void remove(Iterator<E> source, E value) {
      while (source.hasNext()) {
         E candidate = source.next();
         boolean remove = value.equals(candidate);
         if (remove) {
            source.remove();
            }
         }
      }

   /**
    * Removes all the elements from the collection that are equal to the
    * specified value.
    * @param   <E>   the type of the elements.
    * @param   source   the collection.
    * @param   value   the value to remove from the collection.
    */
   public static <E> void remove(Iterable<E> source, E value) {
      remove(source.iterator(), value);
      }

   /**
    * Removes all the elements from the collection that satisfy the predicate.
    * @param   <E>   the type of the elements.
    * @param   source   the start of the collection.
    * @param   predicate   the predicate.
    */
   public static <E> void removeIf(Iterator<E> source, UnaryPredicate<E> predicate) {
      while (source.hasNext()) {
         E candidate = source.next();
         boolean remove = predicate.eval(candidate);
         if (remove) {
            source.remove();
            }
         }
      }

   /**
    * Removes all the elements from the collection that satisfy the predicate.
    * @param   <E>   the type of the elements.
    * @param   source   the collection.
    * @param   predicate   the predicate.
    */
   public static <E> void removeIf(Iterable<E> source, UnaryPredicate<E> predicate) {
      removeIf(source.iterator(), predicate);
      }

   /**
    * Copies into {@code destination} all the elements that are not equal to the
    * specified value.
    * @param   <E>   the type of elements.
    * @param   source   the start of the collection.
    * @param   destination   the place to copy the elements that are not equal.
    * @param   value   the reference value.
    */
   public static <E> void removeCopy(Iterator<E> source, ListIterator<E> destination, E value) {
      while (source.hasNext()) {
         E candidate = source.next();
         boolean copy = !value.equals(candidate);
         if (copy) {
            destination.next();
            destination.set(candidate);
            }
         }
      }

   /**
    * Copies into {@code destination} all the elements that are not equal to the
    * specified value.
    * @param   <E>   the type of elements.
    * @param   source   the collection.
    * @param   destination   the place to copy the elements that are not equal.
    * @param   value   the reference value.
    */
   public static <E> void removeCopy(Iterable<E> source, ListIterator<E> destination, E value) {
      removeCopy(source.iterator(), destination, value);
      }

   /**
    * Copies into {@code destination} all the elements that do not satisfy the
    * specified predicate.
    * @param   <E>   the type of elements.
    * @param   source   the start of the collection.
    * @param   destination   the place to copy the elements that are not equal.
    * @param   predicate   the reference value.
    */
   public static <E> void removeCopyIf(Iterator<E> source, ListIterator<E> destination, UnaryPredicate<E> predicate) {
      while (source.hasNext()) {
         E candidate = source.next();
         boolean copy = !predicate.eval(candidate);
         if (copy) {
            destination.next();
            destination.set(candidate);
            }
         }
      }

   /**
    * Copies into {@code destination} all the elements that do not satisfy the
    * specified predicate.
    * @param   <E>   the type of elements.
    * @param   source   the start of the collection.
    * @param   destination   the place to copy the elements that are not equal.
    * @param   predicate   the reference value.
    */
   public static <E> void removeCopyIf(Iterable<E> source, ListIterator<E> destination, UnaryPredicate<E> predicate) {
      removeCopyIf(source.iterator(), destination, predicate);
      }



// NON-MUTATING
// adjacent_find
// find_first_of
// count
// count_if
// mismatch
// equal
// search
// search_n
// find_end

// MUTATING
// copy
// copy_n
// copy_backward
// swap
// iter_swap
// swap_ranges
// replace
// replace_if
// replace_copy
// replace_copy_if
// fill
// fill_n
// generate
// generate_n
// remove_copy
// remove_copy_if
// unique
// unique_copy
// reverse
// reverse_copy
// rotate
// rotate_copy
// random_shuffle
// random_sample
// random_sample_n
// partition
// stable_partition

// includes
// set_union
// set_intersection
// set_difference
// set_symmetric_difference


   }
